/*
https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/description/
1802.有界数组中指定下标处的最大值
medium, 方钊堉 2024.09.17
二分查找
*/

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        int le = 1, r = maxSum;
         // 二分查找循环，直到左右边界相邻。
        while (le < r) {
            int q=le + r + 1;
            int eee =q/ 2;
            if (valid(eee, n, index, maxSum)) {
                le = eee;
            } else {
                r = eee - 1;
            }
        }
        return le;
    }

// 检查某个值是否可以使数组和不超过 maxSum。
    bool valid(int eee, int n, int index, int maxSum) {
        int le = index;
        int r = n - index - 1;
        // 计算总和，包括中间的最大值。
        return eee + cal(eee, le) + cal(eee, r) <= maxSum;
    }

        long cal(int big, int length) {
        if (length + 1 < big) {
            // 如果长度不足以到达最大值，则计算等差数列的和。
            int small = big - length;
            return (long) (big - 1 + small) * length / 2;
        } else {
            // 如果长度足够到达最大值，则计算剩余部分的和。
            int kkk = length - (big - 1);
            return (long) big * (big - 1) / 2 + kkk;
        }
    }
};